package LearnAlgorithm.d_标准查找算法and标准排序算法;
/**
 * 思路：开辟新的空间，空间大小为max(source)-min(source)+1 
 *    扫描source，将value作为辅助空间的下标，用辅助空间的该位置元素记录value的个数
 *    如：9 7 5 3 1 ，helper=arr(10)
 *    一次扫描，value为9，将helper[9]++，value为7，将helper[7]++……
 *    如此这般之后，我们遍历helper，如果该位（index）的值为0，说明index不曾在source中出现
 *    如果该位（index)的值为1，说明index在source中出现了1次，为2自然是出现了2次
 *    遍历helper就能将source修复为升序排列
 */
/*
时间复杂度:扫描1次source, 扫描1次helper, 复杂度为N+k
空间复杂度:辅助空间k, k=max0f(source)
非原址排序
稳定性:相同元素不会出现交叉，非原址都是拷来拷去
如果要优化一下空间， 可以求minOf(source), helper的长度位max-min+1,这样能短点
计数有缺陷，数据较为密集或范围较小时适用。
 */
public class b8计数排序 {
	public static int[] helper = null; 
	public static void main(String[] args) {
		int[] arr = new int[] {9,8,6,5,4,7,1,10,15,14,16,-6};
		long before = System.currentTimeMillis();
//		countSort(arr, helper, 0);
		countSort(arr, helper);
		util.Util.duration(before);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	/**
	 * 计数排序---解决重复元素和负数
	 * @param arr
	 * @param helper
	 */
	public static void countSort(int[] arr, int[] helper) {
		int min = minFind(arr);
		int current = 0;
		helper = new int[maxFind(arr) + 1 - min];//这里重点；减min这个操作，如果有负数那就是进一步扩展了helper，如果没有负数就是缩减了helper，一石二鸟
		for (int i = 0; i < arr.length; i++) {
			helper[arr[i] - min]++;//打标记的下表发生了改变，需要加上偏移量，也就是减min
		}
		for (int i = 0; i < helper.length; i++) {
			while (helper[i] > 0) {
				arr[current++] = i + min;//这里回填，把偏移量加回来
				helper[i]--;
			}
		}
	}
	
	/**
	 * 计数排序---解决重复元素
	 * O(N)
	 * @param arr
	 * @param helper
	 * @param p
	 * @param r
	 */
	public static void countSort(int[] arr, int[] helper, int p) {
		
		int current = 0;
		helper = new int[maxFind(arr) + 1];//创建辅助空间；+1的目的是让helper存在下表=maxFind(arr)的元素
		for (int i = 0; i < arr.length; i++) {//运用下标意义，给对应辅助空间打上标记
			helper[arr[i]]++;
		}
		for (int i = 0; i < helper.length; i++) {//这里对原数组进行排序
			while (helper[i] > 0) {//从辅助空间的下标意义入手
				/*
				 * 如果helper的一个元素大于0，
				 * 那么这个元素的下标就是可以放入arr中的值；
				 * 放入arr对应的位置后，
				 * 在arr中指向当前的“待放入数值”的指针向下移动一位，也就是current++
				 */
				arr[current++] = i;
				helper[i]--;//因为可能有重复元素，所以把helper[i]--，减减后不为零就代表有重复元素还要接着存入arr
			}
		}
	}
	
	/**
	 * 求数组最大值
	 * O(N)
	 * @param arr
	 * @return
	 */
	public static int maxFind(int[] arr) {
		int max = arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (max <= arr[i]) {
				max = arr[i];
			}
		}
		return max;
	}
	
	/**
	 * 求数组最小值
	 * @param arr
	 * @return
	 */
	public static int minFind(int[] arr) {
		int min = arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] <= min) {
				min = arr[i];
			}
		}
		return min;
	}
}
